package com.leet.code.lcof;

import java.util.LinkedList;

public class Code31 {
    public static void main(String[] args) {

        int[] push = {1, 2, 3, 4, 5};
        int[] pop = {4, 3, 5, 1, 2};
        System.out.println(new Code31().validateStackSequences(push, pop));
    }


    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length == 0) {
            return false;
        }

        int us = 0, os = 0;
        LinkedList<Integer> sk = new LinkedList<>();
        while (true) {
            if (sk.size() != 0 && sk.getLast() == popped[os]) {
                sk.removeLast();
                os++;
            } else if (us == pushed.length) {
                if (sk.size() == 0) {
                    return os == pushed.length;
                }
                return false;
            } else if (pushed[us] == popped[os]) {
                us++;
                os++;
            } else {
                sk.addLast(pushed[us]);
                us++;
            }
        }


    }


}
